\documentclass[table]{beamer}
\usepackage[UTF8, scheme = plain]{ctex}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{esint}
\usepackage{indentfirst}
\usetheme{Madrid}
\usepackage{graphicx}
\usepackage{color}
\usepackage{float}
\usepackage{enumerate}
\usepackage{mathrsfs}
%\usepackage[margin=0.8in]{geometry}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
%\newtheorem{prob}[Example]{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]

\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newtheorem{eg}{Example}
\newtheorem{prob}[eg]{Problem}
\begin{document}
\begin{frame}
\title{Theoretical Homework 1}
\author{Shuang Hu}
\institute{School of Mathematical Science,\\Zhejiang University}
\date{2022.10.13}
\titlepage
\end{frame}
\begin{frame}{Problem1}
\begin{prob}
    Consider the bisection method starting with the initial interval $[1.5,3.5]$. In the following questions "the interval" refers to the bisection interval whose width changes across different loops.
    \begin{itemize}
        \item What is the width of the interval at the $n$th step?
        \item What is the supremum of the distance between the root $r$ and the midpoint of the interval?
    \end{itemize}
\end{prob}
\end{frame}
\begin{frame}{Solution1}
    \begin{proof}
        (1) 第一步循环时，输入的区间为$[1.5,3.5]$，区间长度$l_{1}=2$。根据二分法的叙述，每一步循环过程中输入区间长度减半，即得$l_{n}=2^{2-n}$。

        (2) 设第$n$步二分法循环时区间为$[a_{n},b_{n}]$，记$m_{n}=\frac{b_{n}+a_{n}}{2}$为区间中点，由二分法算法流程可得:
        \begin{equation}
            |r-m_{n}|\le |b_{n}-m_{n}|=\frac{b_{n}-a_{n}}{2}.
        \end{equation}
        从而，该题的答案为$p_{n}=2^{1-n}$。
    \end{proof}
\begin{rem}
    本题有一个歧义：第1步迭代区间到底是指输入二分法程序的区间，还是跑了一步二分法后的区间？如果按前者理解，答案如上；如果按后者理解，则$l_{n}=2^{1-n}$,$p_{n}=2^{-n}$。实际批改时两种答案都算对。
\end{rem}
\end{frame}
\begin{frame}{Problem2}
    \begin{prob}
    In using the bisection algorithm with its initial interval as $[a_{0},b_{0}]$ with $a_{0}>0$, we want to determine the root with its relative error no greater than $\epsilon$. Prove that this goal of accuracy is guaranteed by the following choice of the number of steps,
    \begin{equation}
        n\ge\frac{\log(b_{0}-a_{0})-\log\epsilon-\log a_{0}}{\log 2}.
    \end{equation}
    \end{prob}
    \begin{rem}
        此处和课本上的题目描述有区别，因为第一步迭代区间按照输入二分法程序的区间算。
    \end{rem}
\end{frame}
\begin{frame}{Solution2}
    \begin{proof}
    由第一题(2)可知，第$n$步的绝对误差$\epsilon_{abs}^{n}\le(b_{0}-a_{0})2^{-n}$。又有$a_{0}>0$, $a_{0}<b_{0}$, 可知相对误差
    \begin{equation}
        \epsilon_{rel}^{n}\le\frac{\epsilon_{abs}^{n}}{a_{0}}\le\frac{(b_{0}-a_{0})2^{-n}}{a_{0}}.
    \end{equation}
    由题目条件:\begin{equation}
        n\ge\frac{\log(b_{0}-a_{0})-\log\epsilon-\log a_{0}}{\log 2},
    \end{equation}
    代入$(3)$可得：
    \begin{equation}
        \frac{(b_{0}-a_{0})2^{-n}}{a_{0}}\le\frac{b_{0}-a_{0}}{a_{0}}\frac{\epsilon a_{0}}{b_{0}-a_{0}}\le\epsilon.
    \end{equation}
    符合题意。
    \end{proof}
\end{frame}
\begin{frame}{Problem3}
    \begin{prob}
        Perform four iterations of Newton's method for the polynomial equation $p(x)=4x^3-2x^2+3=0$ with the starting point $x_{0}=-1$. Use a hand calculator and organize results of the iterations in a table.
    \end{prob}
    由牛顿迭代法的公式，可得:
    \begin{equation}
        x_{n+1}=x_{n}-\frac{p(x_{n})}{p'(x_{n})}=x_{n}-\frac{4x_{n}^{3}-2x_{n}^{2}+3}{12x_{n}^{2}-4x_{n}}.
    \end{equation}
    取$x_{0}=-1$，代入公式$(6)$进行迭代计算即可。
    \begin{rem}
        完全没有必要使用分数存储$x_{n}$。
    \end{rem}
\end{frame}
\begin{frame}{Problem4}
    \begin{prob}
        Consider a variation of Newton's method in which only the derivative at $x_{0}$ is used,
        \begin{equation}
            x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{0})}.
        \end{equation}
        Find $C$ and $s$ such that
        \begin{equation}
            e_{n+1}=Ce_{n}^{s}
        \end{equation}
        where $e_{n}$ is the error of Newton's method at step $n$, $s$ is a constant, and $C$ may depend on $x_{n}$, the given function $f$, its derivatives and the exact root $r$.
    \end{prob}
\end{frame}
\begin{frame}{Solution4}
    \begin{proof}
        \begin{equation}
            \begin{aligned}
                &x_{n+1}-r=x_{n}-r-\frac{f(x_{n})}{f'(x_{0})}\\
                \Rightarrow&x_{n+1}-r=x_{n}-r-\frac{f(x_{n})-f(r)}{f'(x_{0})}\\
                \Rightarrow& \frac{x_{n+1}-r}{x_{n}-r}=1-\frac{f(x_{n})-f(r)}{(x_{n}-r)f'(x_{0})}\\
                \Rightarrow& \frac{e^{n+1}}{e^{n}}=1-\frac{f'(\xi)}{f'(x_{0})}.
            \end{aligned}
        \end{equation}
        由Lagrange中值定理，$\xi$与$x_{n},r,f$均相关。取$s=1$，$C=1-\frac{f'(\xi)}{f'(x_{0})}$，满足$(8)$式。
    \end{proof}
\end{frame}
\begin{frame}{Problem5}
    \begin{prob}
    Within $(-\frac{\pi}{2},\frac{\pi}{2})$, will the iteration $x_{n+1}=\arctan x_{n}$ converge?
    \end{prob}
    "Solution":$f'(x)=\frac{1}{x^2+1}\le 1$，由压缩映射原理，$x_{n}$收敛。
    \begin{rem}
        Why the "solution" above is incorrect?
    \end{rem}
\end{frame}
\begin{frame}{Solution}
    对于$x_{0}\in(0,\frac{\pi}{2})$，由归纳原理，$x_{n}>0$。又
    \begin{equation}
        x_{n}=\tan x_{n+1}\ge x_{n+1},
    \end{equation}
    可知$x_{n}$单调递减，且有下界0，故该序列收敛。

    如果$x_{0}\in(-\frac{\pi}{2},0)$，类似的讨论可知$x_{n}$单调递增有上界0，故该序列收敛。

    如果$x_{0}=0$，计算即得$x_{n}\equiv 0$，收敛。

    综上所述，$x_{n}$收敛于0。
\end{frame}
\begin{frame}{Problem6}
    \begin{prob}
        Let $p>1$. What is the value of the following continued fraction?
        \begin{equation}
            x=\frac{1}{p+\frac{1}{p+\frac{1}{p+\cdots}}}.
        \end{equation}
    \end{prob}
    "Solution": set $x_{1}=\frac{1}{p}$, $x_{2}=\frac{1}{p+\frac{1}{p}}$, $x_{3}=\frac{1}{p+\frac{1}{p+\frac{1}{p}}}\cdots$, it's "clear" that $x_{n}$ is monotonically decreasing, so $x_{n}$ converge. While $\frac{1}{x_{n+1}}=x_{n}+p$, set $n\rightarrow\infty$, $x_{n}$ converges to $\frac{-p+\sqrt{p^2+4}}{2}$.
    \begin{rem}
        Why the "solution" above is incorrect?
    \end{rem}
\end{frame}
\begin{frame}{Solution6}
    将$(11)$式转化为不动点迭代问题，如下：
    \begin{equation}
        x_{n+1}=\frac{1}{x_{n}+p}.
    \end{equation}
    由于$x_{0}>0$，由归纳原理，$x_{n}>0$。
    对于函数$f(x)=\frac{1}{x+p}$，计算$f'(x)=-\frac{1}{(x+p)^{2}}$，可得$|f'(x)|=\frac{1}{(x+p)^{2}}<\frac{1}{p^2}<1$。由压缩映射原理，$x_{n}$收敛。设$x_{n}$收敛于$x$，两边同取极限，得：
    \begin{equation}
        x=\frac{1}{x+p}.
    \end{equation}
    可知$x=\frac{-p+\sqrt{p^2+4}}{2}$。
\end{frame}
\begin{frame}{Problem7}
    \begin{prob}
        What happens in problem II if $a_{0}<0<b_{0}$? Derive an inequality of the number of steps similar to that in II. In this case, is the relative error still an appropriate measure?
    \end{prob}
    绝对误差同II，可以写$\epsilon_{abs}^{n}\le(b_{0}-a_{0})2^{-n}$。由于$a_{0}<0<b_{0}$且$r\in(a_{0},b_{0})$，如果$r\approx 0$，相对误差$\epsilon_{rel}\rightarrow\infty$，所以该情形下相对误差并不是一个好的度量。
\end{frame}
\begin{frame}
    Thanks!

    Questions?
\end{frame}
\end{document}